1. Field of the Invention
This invention relates to software testing. More particularly this invention relates to the automatic generation of test programs for a software implementation that has been modeled as a finite state machine.
2. Description of the Related Art
In the field of hardware, testing it is common to treat the device under test as a finite state machine (FSM). It has been proposed to similarly automate software testing by similarly representing the software program as a finite state machine, in which transitions are represented as directed edges between states. However, the number of tests required to exhaustively exercise a software program is typically much larger than is required for hardware. Furthermore resources for test execution are limited, and their use constitutes a cost. Accordingly, test engineers have attempted to selectively reduce the number of tests in order that the test generation process be practical in terms of cost and execution time, recognizing that the testing process must still be reliable. Explosion of the number of test programs that are generated by automatic techniques is a drawback of automatic test program generation.
Test engineers use finite state machines to model externally observable behavior, and then use various tools to traverse paths of test actions that connect a sequence of states They then generate test cases for a variety of purposes, for example acceptance suites, full functional test suites, and regression test suites. Regression test suites involve a rerun of selected portions of a test suite following a revision of an application.
Because a finite state machine that reflects the specification of a useful software program is typically very large, various approaches have been taken to manage the model, using concise and powerful graphical and textual languages. Various traversal algorithms are applied to the finite state machine for test generation. These algorithms are parameterized by the test engineer at runtime.
The generation of an astronomical number of possible test cases is a well-known software testing problem, which has been exacerbated by the speed of automated test generation. Test engineers deal with this by identifying “equivalence classes” for various attributes of test cases. For example, for a function call argument that must fall within the range of 1 to 5, a test engineer may decide to test the minimum value (1), the maximum value (5), and one value that falls between the minimum and the maximum, such as the value (2). With these decisions, the test engineer places the values (2), (3), and (4) in an “equivalence class”. Each value is considered equivalent to the other two, in the sense that if the test fails for any value in the class, then it will fail for all other values of the class. The recognition of equivalence classes stems from the recognition of inherent properties of the software being tested. In theory, there is one “true” set of equivalence classes for a particular program. Once these classes are correctly ascertained, they will remain static throughout the testing period, or until the software application under test is significantly changed.
Conventional approaches to test generation have common problems that this invention builds upon. In each case, the number of unique paths, or generated test programs is an exponential function of the number of modeled states and transitions. Thus as the scope of the modeled behavior grows, the time to exhaustively generate test cases, and more significantly, the time needed to execute the generated test cases grows exponentially. This growth places a practical limit on the complexity of the program behavior to which automated test generation can be applied. The invention focuses and therefore reduces the number of tests to a practical level. In so doing, the invention raises the practical limit on the complexity of the software program to which automated test generation may be applied.
A common test planning heuristic is “suspicion testing”, in which “suspected” features of the program are evaluated. For example, aspects of the program that are inherently difficult to implement are suspected to have a relatively high probability of containing defects.
In other approaches, constraints have been imposed on paths or transitions, and if not satisfied, the path would not be tested further.
Typical of prior art approaches for generating test programs is U.S. Pat. No. 5,394,347 to Kita et al. which discloses a method of modeling a specification as an extended finite state machine, then performing a depth-first traversal of the resulting state diagram to generate a path file as a basis for a test program.
U.S. Pat. No. 5,623,499 to Ko et al. discloses a technique for generating a test data sequence of minimal length, employing an extended finite state machine. This technique attempts to balance the number of traversals of the directed edges in order to test values in a predetermined test data set. The test data sequence is constructed using an Euler tour.
In U.S. Pat. No. 5,918,037 to Tremblay et al., it is proposed to employ a test generator that automatically produces test programs based on a finite state machine model of the software. Limiting the number of test programs is achieved by controlling loop execution, and by appropriately setting the coverage level for the model, known as “transition cover testing”. This approach seeks to specify during the test program generation process that each transition within the finite state machine model be exercised once. The generator is capable of specifying different coverage levels for selected portions of the program under test, so that critical portions might be exhaustively tested, while other portions receive less comprehensive testing.
There are several reasons for focusing test program generation. Some may be unanticipated during the development and implementation of the software specification. For example, the testing process may uncover programming defects. Such discovery may create the need to generate still more tests that work around the newly discovered defect in order to test unaffected parts of the software. Once the defect has been corrected, even more tests may need to be generated in order for verification. In practice, a supposedly corrected defect may surface again following subsequent program modification, or changes in the conditions of usage. Thus, it is desirable to repeatedly verify that the defect has not recurred.
The task has fallen to software engineers to revise test programs to accommodate incremental changes in the software program. As there is a cost in the generation of test models, engineers archive and reuse the products of the test generation process. While the archival technique is generally practical, maintaining compatible archived test programs has itself been proven costly. Furthermore, ad hoc practices of cataloging, finding, and retrieving combinations of test generation parameters are impractical. Because of the lack of alternatives, test engineers often are compelled to resort to archiving entire test suites, which is relatively costly.
It would be desirable to be able to automatically create test programs directed at narrowed targets in a manner that allows more compact archival of data objects that can be readily retrieved and reused when it becomes necessary to retest a software application, or for use in testing different software applications.